<!DOCTYPE html>
<html lang="zh-cn">
  <head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta name="author" content="Zhou Wei <zromyk@163.com>">
  <title>leetcode</title>
  <link rel="shortcut icon" href="/favicon.ico">
  <link rel="stylesheet" href="/style/html/pure.css">
  <link rel="stylesheet" href="/style/html/main.css">
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.css">
  <!-- <link rel="stylesheet" href="https://apps.bdimg.com/libs/highlight.js/9.1.0/styles/default.min.css"> -->
<link rel="stylesheet" href="/style/article/highlight/default.min.css">
<link rel="stylesheet" href="/style/article/pell-1.0.6/dist/pell.css">

</head>
<body>
  <div id="menu-background"></div>
  <div id="menu">
    <div class="pure-menu pure-menu-horizontal">
  <ul class="pure-menu-list block-middle">
    <li class="pure-menu-item">
  <a class="pure-menu-heading" href="/index.html">ZROMYK</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/index.html">主页</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/archive/index.html">归档</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/download/index.html">下载</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/feedback/index.html">反馈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="/public/about/index.html">关于我</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link" href="https://github.com/zromyk"><i class="fa fa-github" style="font-size:32px"></i></a>
</li>

  </ul>
</div>

  </div>
  <div id="layout">
    <div class="content">
      <div id="nav">
    <div id="navigation" class="navigation">
  <ul class="pure-menu-list">
    <li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#3"><a href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/">3. 无重复字符的最长子串</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_1">方法一：数组保存位置法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_2">方法二：滑动窗口法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#39"><a href="https://leetcode-cn.com/problems/combination-sum/">39. 组合总和</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_3">回溯法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#40-ii"><a href="https://leetcode-cn.com/problems/combination-sum-ii/">40. 组合总和 II</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_4">回溯法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#41"><a href="https://leetcode-cn.com/problems/first-missing-positive/">41. 缺失的第一个正数</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_5">用数组储存是否出现该数字</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#50-powx-n"><a href="https://leetcode-cn.com/problems/powx-n/">50. Pow(x, n)</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_6">假设模拟</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_7">算法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#82-ii"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/">82. 删除排序链表中的重复元素 II</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_8">一般做法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#53"><a href="https://leetcode-cn.com/problems/maximum-subarray/">53. 最大子序和</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#1">1. 贪心算法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#2">2. 动态规划</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#54"><a href="https://leetcode-cn.com/problems/spiral-matrix/">54. 螺旋矩阵</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#83"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/">83. 删除排序链表中的重复元素</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#206"><a href="https://leetcode-cn.com/problems/reverse-linked-list/">206. 反转链表</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#1_1">1. 一般迭代法：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#2_1">2. 两次交换迭代法：</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#3_1">3. 尾递归法</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#92-ii"><a href="https://leetcode-cn.com/problems/reverse-linked-list-ii/">92. 反转链表 II</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#264-ii"><a href="https://leetcode-cn.com/problems/ugly-number-ii/">264. 丑数 II</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_9">动态规划</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#456-132"><a href="https://leetcode-cn.com/problems/132-pattern/">456. 132 模式</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_10">方法一：单调递减栈</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#1019"><a href="https://leetcode-cn.com/problems/next-greater-node-in-linked-list/">1019. 链表中的下一个更大节点</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#k"><a href="https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=188&amp;tqId=38279&amp;rp=1&amp;ru=%2Factivity%2Foj&amp;qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&amp;tab=answerKey">最小的 K 个数</a></a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_11">方法一：快排</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#_12">方法二：优先队列（小顶堆）</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#_13">两数之和</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#map">map</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav5" onclick="animateByNav()" href="#unordered_map">unordered_map</a>
</li>
<li class="pure-menu-item">
  <a class="pure-menu-link nav4" onclick="animateByNav()" href="#_14"><a href="https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=188&amp;tqId=38293&amp;rp=1&amp;ru=%2Fta%2Fjob-code-high-week&amp;qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&amp;tab=answerKey">最长无重复子串</a></a>
</li>

  </ul>
</div>

</div>
<div id="content-articles">
  <h1 id="leetcode" class="content-subhead">leetcode</h1>
  <p>
    <span>2021-03-24</span>
    <span><span class="post-category post-category-algorithm">Algorithm</span></span>
    <button id="button-markdownEditor" class="pure-button" onclick="markdownEditor()">启用编辑</button>
    <button id="button-save" class="pure-button" onclick="save()">保存</button>
  </p>
  <div id="content-articles-markdownEditor" style="display: none;">
    <h1>编辑 power by pell</h1>
    <div id="editor" class="pell"></div>
    <div style="margin-top:20px;">
        <h3>Text output:</h3>
        <div id="text-output"></div>
    </div>
    <div style="margin-top:20px;">
        <h3>HTML output:</h3>
        <pre id="html-output"></pre>
    </div>
  </div>
  <div id="content-articles-markdown">
    <h4 id="3"><a href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/">3. 无重复字符的最长子串</a></h4>
<p><strong>题目描述：</strong></p>
<p>给定一个字符串，请你找出其中不含有重复字符的 <strong>最长子串</strong> 的长度。</p>
<p><strong>示例 :</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入: s = &quot;abcabcbb&quot;
输出: 3 
解释: 因为无重复字符的最长子串是 &quot;abc&quot;，所以其长度为 3。

输入: s = &quot;bbbbb&quot;
输出: 1
解释: 因为无重复字符的最长子串是 &quot;b&quot;，所以其长度为 1。

输入: s = &quot;pwwkew&quot;
输出: 3
解释: 因为无重复字符的最长子串是 &quot;wke&quot;，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，&quot;pwke&quot; 是一个子序列，不是子串。

输入: s = &quot;&quot;
输出: 0
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0 &lt;= s.length &lt;= 5 * 104</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>s</code></span> 由英文字母、数字、符号和空格组成</li>
</ul>
<h5 id="_1">方法一：数组保存位置法</h5>
<p>执行用时：8 ms, 在所有 C++ 提交中击败了88.77%的用户</p>
<p>内存消耗：6.8 MB, 在所有 C++ 提交中击败了87.98%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int local[128]; // 记录对应字符出现的位置
        int start, left, right, size = 0;

        for (left = 0; left &lt; s.length(); ++left) 
        {
            memset(local, -1, sizeof(int)*128); // 全部设置为 -1 表示对应字符未出现过
            local[s[left]] = left;
            start = left;

            for (right = left + 1; right &lt; s.length(); ++right) {
                if (local[s[right]] != -1) { // 该字符之前已经出现过
                    left = local[s[right]]; // left = local[s[right]]; 跳过下面注释的 'f'
                    break;
                }
                local[s[right]] = right; // 在 local 数组上，记录下当前字符的位置
            }
            /*   
                start
                 |
                &quot;afbtbcbb&quot;
                   | |
                   | right
                   left
            */
            size = max(size, right - start);
        }
        return size;
    }
};
</code></span></code></pre>
<h5 id="_2">方法二：滑动窗口法</h5>
<p>执行用时：4 ms, 在所有 C++ 提交中击败了97.39%的用户</p>
<p>内存消耗：7.3 MB, 在所有 C++ 提交中击败了75.15%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if(len == 0){ return 0; }
        vector&lt;int&gt; window(128, 0);
        int left = 0, right = 0, size = 0;

        while (right &lt; len) {
            while (window[s[right]] &gt; 0) {
                window[s[left]]--;
                left++;
            }
            window[s[right]]++;
            size = max(size, right - left + 1);
            right++;
        }
        return size;
    }
};
</code></span></code></pre>
<blockquote class="content-quote">
<p>回溯类似题解：</p>
<ul>
<li>
<p><a href="https://leetcode-cn.com/problems/combination-sum/">39.组合总和</a></p>
</li>
<li>
<p><a href="https://leetcode-cn.com/problems/combination-sum-ii/">40. 组合总和 II</a></p>
</li>
<li>
<p><a href="https://leetcode-cn.com/problems/permutations/">46. 全排列</a></p>
</li>
<li>
<p><a href="https://leetcode-cn.com/problems/permutations-ii/">47. 全排列 II</a></p>
</li>
<li>
<p><a href="https://leetcode-cn.com/problems/subsets/">78. 子集</a></p>
</li>
<li>
<p><a href="https://leetcode-cn.com/problems/subsets-ii/">90. 子集 II</a></p>
</li>
</ul>
</blockquote>
<h4 id="39"><a href="https://leetcode-cn.com/problems/combination-sum/">39. 组合总和</a></h4>
<p><strong>题目描述：</strong></p>
<p>给定一个无重复元素的数组 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 和一个目标数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>target</code></span> ，找出 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 中所有可以使数字和为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>target</code></span> 的组合。</p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 中的数字可以无限制重复被选取。</p>
<p><strong>说明：</strong></p>
<p>所有数字（包括<span style="overflow-x: auto; max-width:100%; display:inline;"><code>target</code></span>）都是正整数。</p>
<p>解集不能包含重复的组合。 </p>
<p><strong>提示：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
</code></span></code></pre>
<p><strong>提示：</strong></p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= candidates.length &lt;= 30</code></span><br />
<span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= candidates[i] &lt;= 200</code></span><br />
<span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidate</code></span> 中的每个元素都是独一无二的。<br />
<span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= target &lt;= 500</code></span></p>
<h5 id="_3">回溯法</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;vector&lt;int&gt;&gt; result;

    vector&lt;vector&lt;int&gt;&gt; combinationSum(vector&lt;int&gt;&amp; candidates, int target) {
        // sort(candidates.begin(), candidates.end());
        vector&lt;int&gt; temp;
        dfs(temp, candidates, target, 0);
        return result;
    }

    void dfs(vector&lt;int&gt; &amp;temp, vector&lt;int&gt;&amp; candidates, int target, int loc) {
        if (target &lt;  0) { return; }
        if (target == 0) { 
            result.push_back(temp); 
            return;
        }
        for (int i = loc; i &lt; candidates.size(); ++i) {
            temp.push_back(candidates[i]);
            dfs(temp, candidates, target - candidates[i], i);
            temp.pop_back();
        }
    }
};
</code></span></code></pre>
<h4 id="40-ii"><a href="https://leetcode-cn.com/problems/combination-sum-ii/">40. 组合总和 II</a></h4>
<p><strong>题目描述：</strong></p>
<p>给定一个数组 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 和一个目标数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>target</code></span> ，找出 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 中所有可以使数字和为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>target</code></span> 的组合。</p>
<p><span style="overflow-x: auto; max-width:100%; display:inline;"><code>candidates</code></span> 中的每个数字在每个组合中只能使用一次。</p>
<p><strong>说明：</strong></p>
<p>所有数字（包括目标数）都是正整数。</p>
<p>解集不能包含重复的组合。 </p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
</code></span></code></pre>
<h5 id="_4">回溯法</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;vector&lt;int&gt;&gt; result;

    vector&lt;vector&lt;int&gt;&gt; combinationSum2(vector&lt;int&gt;&amp; candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector&lt;int&gt; temp;
        dfs(temp, candidates, target, 0);
        return result;
    }

    void dfs(vector&lt;int&gt; &amp;temp, vector&lt;int&gt;&amp; candidates, int target, int loc) {
        if (target &lt;  0) { return; }
        if (target == 0) { 
            result.push_back(temp); 
            return;
        }
        for (int i = loc; i &lt; candidates.size(); ++i) {
            temp.push_back(candidates[i]);
            if (i == loc || candidates[i] != candidates[i-1]) { // 去重
                dfs(temp, candidates, target - candidates[i], i+1); // i+1
            }
            temp.pop_back();
        }
    }
};
</code></span></code></pre>
<h4 id="41"><a href="https://leetcode-cn.com/problems/first-missing-positive/">41. 缺失的第一个正数</a></h4>
<p><strong>问题描述：</strong></p>
<p>给你一个未排序的整数数组 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums</code></span> ，请你找出其中没有出现的最小的正整数。</p>
<p>进阶：你可以实现时间复杂度为 <script type="math/tex">O(n)</script> 并且只使用常数级别额外空间的解决方案吗？</p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：nums = [1,2,0]
输出：3

输入：nums = [3,4,-1,1]
输出：2

输入：nums = [7,8,9,11,12]
输出：1
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>0 &lt;= nums.length &lt;= 300</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-231 &lt;= nums[i] &lt;= 231 - 1</code></span></li>
</ul>
<h5 id="_5">用数组储存是否出现该数字</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int firstMissingPositive(vector&lt;int&gt;&amp; nums) {
        if (nums.empty()) { return 1; }
        vector&lt;bool&gt; temp(nums.size() + 1);

        for (int i = 0; i &lt; nums.size(); ++i) {
            if (0 &lt; nums[i] &amp;&amp; nums[i] &lt;= nums.size()) { // 关键点
                temp[nums[i]] = true;
            }
        }
        for (int i = 1; i &lt; temp.size(); ++i) {
            if (temp[i] == false) {
                return i;
            }
        }
        return temp.size();
    }
};
</code></span></code></pre>
<h4 id="50-powx-n"><a href="https://leetcode-cn.com/problems/powx-n/">50. Pow(x, n)</a></h4>
<p><hard>中等</hard></p>
<p><strong>题目描述：</strong></p>
<p>实现 <a href="https://www.cplusplus.com/reference/valarray/pow/">pow(<em>x</em>, <em>n</em>)</a> ，即计算 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>x</code></span> 的 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span> 次幂函数（即，<script type="math/tex">x^n</script>）。</p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-100.0 &lt; x &lt; 100.0</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-231 &lt;= n &lt;= 231-1</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-104 &lt;= x^n &lt;= 104</code></span></li>
</ul>
<h5 id="_6">假设模拟</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：x = 2.00000, n = 10
</code></span></code></pre>
<p>
<script type="math/tex; mode=display">
\begin{array}{c} 
n : &[1] & [2] & [3] & 4 & [5] & 6 & 7 & [8] & 9 & 10 & 11 & 12 & [13] & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 
 & [21] & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 33 & 32 & 33 & [34] & 35 & 36 & 37 & 38 & 39 & 40 \\
 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 & 53 & 52 & [55] & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\
 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 & 73 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\
 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & [89] & 90 & 93 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \\
\end{array}
</script>
</p>
<p>初步想法：先用上述规律计算 <script type="math/tex">x^n</script> 的值 <script type="math/tex">x^{n_{new}} = x^{n_{max}} * x^{n_{second-max}}</script> ，并且保存在数组中。</p>
<p>如 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n = 100</code></span>， 先计算 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n = 1, 2, 3, 5, 8, 13, 24, 55, 89</code></span> 时的 <script type="math/tex">x^n</script> 保存在数组中。</p>
<p>继续计算  <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n = 100-89 = 11</code></span> 时最接近的值，即 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n = 11-8 = 3</code></span>，最后得出结果。</p>
<p>未完待续 &hellip;</p>
<h5 id="_7">算法</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    double myPow(double x, int n) {
        double res = 1.0;
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 != 0) {
                res *= x;
            }
            x *= x;
        }
        return  n &lt; 0 ? 1 / res : res;
    }
};
</code></span></code></pre>
<h4 id="82-ii"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/">82. 删除排序链表中的重复元素 II</a></h4>
<p><hard>中等</hard></p>
<p><strong>题目描述：</strong></p>
<p>存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。</p>
<p>返回同样按升序排列的结果链表。</p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

输入：head = [1,1,1,2,3]
输出：[2,3]
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li>链表中节点数目在范围 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>[0, 300]</code></span> 内</li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-100 &lt;= Node.val &lt;= 100</code></span></li>
<li>题目数据保证链表已经按升序排列</li>
</ul>
<h5 id="_8">一般做法</h5>
<p>执行用时：4 ms, 在所有 C++ 提交中击败了98.49%的用户</p>
<p>内存消耗：10.9 MB, 在所有 C++ 提交中击败了41.13%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode newHead(0, head); // 创建新头节点，next 为旧头节点
        ListNode *cur = &amp;newHead; // 指向当前处理的节点
        int deleteNum; // 要删除的重复数字

        while (cur != nullptr) {
            // 当前节点的next和next-&gt;next都存在且相等，则记录next的值，将后面所有值相同的节点删除
            while (cur-&gt;next != nullptr &amp;&amp; cur-&gt;next-&gt;next != nullptr
                &amp;&amp; cur-&gt;next-&gt;val == cur-&gt;next-&gt;next-&gt;val) 
            {
                deleteNum = cur-&gt;next-&gt;val; // 记录删除值
                while (cur-&gt;next != nullptr) { // 删除操作
                    if (cur-&gt;next-&gt;val != deleteNum) { break; }
                    cur-&gt;next = cur-&gt;next-&gt;next;
                }
            }
            cur = cur-&gt;next;
        }
        return newHead.next;
    }
};
</code></span></code></pre>
<h4 id="53"><a href="https://leetcode-cn.com/problems/maximum-subarray/">53. 最大子序和</a></h4>
<p>给定一个整数数组 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums</code></span> ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [-100000]
输出：-100000
</code></span></code></pre>
<h5 id="1">1. 贪心算法</h5>
<p>执行用时：4 ms, 在所有 C++ 提交中击败了96.36%的用户</p>
<p>内存消耗：12.9 MB, 在所有 C++ 提交中击败了46.07%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int maxSubArray(vector&lt;int&gt;&amp; nums) {
        int pre = 0, maxAns = nums[0];
        for (int i = 0; i &lt; nums.size(); ++i) {
            pre = nums[i] + max(pre, 0);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};
</code></span></code></pre>
<h5 id="2">2. 动态规划</h5>
<p>执行用时：4 ms, 在所有 C++ 提交中击败了96.36%的用户</p>
<p>内存消耗：12.8 MB, 在所有 C++ 提交中击败了68.71%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int maxSubArray(vector&lt;int&gt;&amp; nums) {
        int maxAns = nums[0];
        for (int i = 1; i &lt; nums.size(); ++i) {
            nums[i] = nums[i] + max(nums[i-1], 0);
            maxAns = max(maxAns, nums[i]);
        }
        return maxAns;
    }
};
</code></span></code></pre>
<h4 id="54"><a href="https://leetcode-cn.com/problems/spiral-matrix/">54. 螺旋矩阵</a></h4>
<p><strong>题目描述：</strong></p>
<p>给你一个 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>m</code></span> 行 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span> 列的矩阵 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>matrix</code></span> ，请按照 <strong>顺时针螺旋顺序</strong> ，返回矩阵中的所有元素。</p>
<p><img class="pure-img" alt="img" src="https://zromyk.gitee.io/myblog-figurebed/post/leetcode.assets/spiral1.jpg" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
</code></span></code></pre>
<p><img class="pure-img" alt="img" src="https://zromyk.gitee.io/myblog-figurebed/post/leetcode.assets/spiral.jpg" /></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
</code></span></code></pre>
<p>执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户</p>
<p>内存消耗：6.6 MB, 在所有 C++ 提交中击败了72.83%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; spiralOrder(vector&lt;vector&lt;int&gt; &gt;&amp; matrix) {
        vector&lt;int&gt; result;
        int r = 0, c = -1;

        int move_r[4] = {0, 1, 0, -1};
        int move_c[4] = {1, 0, -1, 0};
        int remainStep[2] = {
            static_cast&lt;int&gt;(matrix[0].size()), 
            static_cast&lt;int&gt;(matrix.size())
        };
        int dirStep = 0;
        int dir = 0;

        while (remainStep[0] &gt; 0 &amp;&amp; remainStep[1] &gt; 0) 
        {
            r += move_r[dir];
            c += move_c[dir];
            result.push_back(matrix[r][c]); 
            if (++dirStep &gt;= remainStep[dir &amp; 0x01]) {
                dirStep = 0;
                dir = (dir + 1) &amp; 0x03;
                remainStep[dir &amp; 0x01]--;
            }
        }
        return result;
    }
};
</code></span></code></pre>
<h4 id="83"><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/">83. 删除排序链表中的重复元素</a></h4>
<p><hard>简单</hard></p>
<p><strong>题目描述：</strong></p>
<p>存在一个按升序排列的链表，给你这个链表的头节点 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>head</code></span> ，请你删除所有重复的元素，使每个元素 <strong>只出现一次</strong> 。</p>
<p>返回同样按升序排列的结果链表。</p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：head = [1,1,2]
输出：[1,2]

输入：head = [1,1,2,3,3]
输出：[1,2,3]
</code></span></code></pre>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *cur = head; // 指向当前处理的节点

        while (cur != nullptr) {
            // 当前节点的next和next-&gt;next都存在且相等
            while (cur-&gt;next != nullptr &amp;&amp; cur-&gt;val == cur-&gt;next-&gt;val) {
                cur-&gt;next = cur-&gt;next-&gt;next;
            }
            cur = cur-&gt;next;
        }
        return head;
    }
};
</code></span></code></pre>
<h4 id="206"><a href="https://leetcode-cn.com/problems/reverse-linked-list/">206. 反转链表</a></h4>
<p><strong>问题描述：</strong></p>
<p>反转一个单链表。</p>
<p><strong>示例：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL
输出: 5-&gt;4-&gt;3-&gt;2-&gt;1-&gt;NULL
</code></span></code></pre>
<h5 id="1_1">1. 一般迭代法：</h5>
<p>执行用时：8 ms, 在所有 C++ 提交中击败了69.86%的用户</p>
<p>内存消耗：8 MB, 在所有 C++ 提交中击败了78.21%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

/*

NULL    1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
｜      ｜
prev    cur

NULL    1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
｜      ｜    ｜
prev    cur  next

NULL &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
｜      ｜   ｜
prev    cur  next

NULL &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
        ｜   ｜
        cur  next
        prev

NULL &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
        ｜   ｜
        prev cur
             next
*/

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *cur = head;
        ListNode *next = nullptr;

        while (cur != nullptr) {
            next = cur-&gt;next;
            cur-&gt;next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};
</code></span></code></pre>
<h5 id="2_1">2. 两次交换迭代法：</h5>
<p>执行用时：8 ms, 在所有 C++ 提交中击败了69.86%的用户</p>
<p>内存消耗：8.1 MB, 在所有 C++ 提交中击败了56.73%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/*

1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; null

null    1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; null
|       |
prev    head

null &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; null
       |     |
       head  prev

null &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; null
       |     |
        prev head

///  两次交换的极简做法 ///

*/

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;

        while (head != nullptr) {
            swap(prev, head-&gt;next);
            swap(prev, head);
        }
        return prev;
    }
};
</code></span></code></pre>
<h5 id="3_1">3. 尾递归法</h5>
<p>执行用时：4 ms, 在所有 C++ 提交中击败了96.83%的用户（最快的一次）</p>
<p>内存消耗：8 MB, 在所有 C++ 提交中击败了88.16%的用户</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/*

1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; null

null    1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; null
|       |
prev    cur

null    1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; null
|       |    |
prev    cur  next

null &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; null
|       |    |
prev    cur  next

null &lt;- 1    2 -&gt; 3 -&gt; 4 -&gt; null
        |    |
        prev cur

/// 执行的单步过程和方法1完全一样 ///

*/

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }

    ListNode* reverse(ListNode* prev, ListNode* cur) {
        if (cur == nullptr) { return prev; } 
        ListNode *next = cur-&gt;next;
        cur-&gt;next = prev;
        return reverse(cur, next);
    }
};
</code></span></code></pre>
<h4 id="92-ii"><a href="https://leetcode-cn.com/problems/reverse-linked-list-ii/">92. 反转链表 II</a></h4>
<p>给你单链表的头指针 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>head</code></span> 和两个整数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>left</code></span> 和 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>right</code></span> ，其中 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>left</code></span> &lt;= <span style="overflow-x: auto; max-width:100%; display:inline;"><code>right</code></span> 。请你反转从位置 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>left</code></span> 到位置 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>right</code></span> 的链表节点，返回 反转后的链表 。</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li>链表中节点数目为 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= n &lt;= 500</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-500 &lt;= Node.val &lt;= 500</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= left &lt;= right &lt;= n</code></span></li>
</ul>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

/*
prev cur
0 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

prev cur  next
0 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

prev cur  next
0 -&gt; 1    2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL
       ------&gt;

prev cur  next
0 -&gt; 1    2    3 -&gt; 4 -&gt; 5 -&gt; NULL
       ------&gt;
       &lt;-

prev cur  next
0    1    2    3 -&gt; 4 -&gt; 5 -&gt; NULL
       ------&gt;
       &lt;-
  ------&gt;

prev next cur
0 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

///////////////////////////////////////////
prev      cur  next
0 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

prev      cur  next
0 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

prev      cur  next
0 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; NULL

prev      cur  next
0 -&gt; 2 -&gt; 1    3 -&gt; 4 -&gt; 5 -&gt; NULL
            ------&gt;

prev      cur  next
0 -&gt; 2 -&gt; 1    3    4 -&gt; 5 -&gt; NULL
            ------&gt;
       &lt;------

prev      cur  next
0    2 -&gt; 1    3    4 -&gt; 5 -&gt; NULL
            ------&gt;
       &lt;------
  ------------&gt;

prev      cur  next
0 -&gt; 3 -&gt; 2 -&gt; 1 -&gt; 4 -&gt; 5 -&gt; NULL

////////////////////////////////////
.
.
.

*/

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode newHead = ListNode(0, head);
        ListNode *prev = &amp;newHead;
        ListNode *cur = nullptr;
        ListNode *next = nullptr;

        for (int i = 1; i &lt; left; ++i) {
            prev = prev-&gt;next;
        }
        cur = prev-&gt;next;
        for (int i = left; i &lt; right; ++i) {
            next = cur-&gt;next;
            cur-&gt;next = next-&gt;next;
            next-&gt;next = prev-&gt;next;
            prev-&gt;next = next;
        }
        return newHead.next;
    }
};
</code></span></code></pre>
<h4 id="264-ii"><a href="https://leetcode-cn.com/problems/ugly-number-ii/">264. 丑数 II</a></h4>
<p><strong>问题描述：</strong></p>
<p>给你一个整数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span> ，请你找出并返回第 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span> 个 <strong>丑数</strong> 。</p>
<p><strong>丑数</strong> 就是只包含质因数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>2</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>3</code></span> 和/或 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>5</code></span> 的正整数。</p>
<p><strong>示例 1：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
</code></span></code></pre>
<p><strong>示例 2：</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：n = 1
输出：1
解释：1 通常被视为丑数。
</code></span></code></pre>
<p><strong>提示：</strong></p>
<p>1 &lt;= n &lt;= 1690</p>
<h5 id="_9">动态规划</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int nthUglyNumber(int n) {
        vector&lt;int&gt; v(1, 1);
        int i = 0, j = 0,  k = 0;

        while (--n) {
            int t = min(v[i] * 2, min(v[j] * 3, v[k] * 5));
            if (v[i] * 2 == t) i++;
            if (v[j] * 3 == t) j++;
            if (v[k] * 5 == t) k++;
            v.push_back(t);
        }
        return v.back();
    }
};
</code></span></code></pre>
<h4 id="456-132"><a href="https://leetcode-cn.com/problems/132-pattern/">456. 132 模式</a></h4>
<p><strong>题目描述：</strong></p>
<p>给你一个整数数组 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums</code></span> ，数组中共有 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>n</code></span> 个整数。<span style="overflow-x: auto; max-width:100%; display:inline;"><code>132</code></span> 模式的子序列 由三个整数 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums[i]</code></span>、<span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums[j]</code></span> 和 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums[k]</code></span> 组成，并同时满足：<span style="overflow-x: auto; max-width:100%; display:inline;"><code>i &lt; j &lt; k</code></span> 和 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums[i] &lt; nums[k] &lt; nums[j]</code></span> 。</p>
<p>如果 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>nums</code></span> 中存在 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>132</code></span> 模式的子序列 ，返回 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>true</code></span> ；否则，返回 <span style="overflow-x: auto; max-width:100%; display:inline;"><code>false</code></span> 。</p>
<p>进阶：很容易想到时间复杂度为 <script type="math/tex">O(n^2) </script>的解决方案，你可以设计一个时间复杂度为 <script type="math/tex">O(n \log n)</script> 或 <script type="math/tex">O(n)</script> 的解决方案吗？</p>
<p><strong>示例 :</strong></p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
</code></span></code></pre>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
</code></span></code></pre>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code>输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
</code></span></code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>n == nums.length</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>1 &lt;= n &lt;= 104</code></span></li>
<li><span style="overflow-x: auto; max-width:100%; display:inline;"><code>-109 &lt;= nums[i] &lt;= 109</code></span></li>
</ul>
<h5 id="_10">方法一：单调递减栈</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    bool find132pattern(vector&lt;int&gt;&amp; nums) {
        int numk = INT_MIN; // 最小值
        stack&lt;int&gt; monoStack; // 单调递减栈

        for (int i = nums.size()-1; i &gt;= 0; --i) {
            if (nums[i] &lt; numk) { 
                return true; 
            }
            // -- 维护单调递减栈 --
            while (monoStack.size() &gt; 0 &amp;&amp; nums[i] &gt; monoStack.top()) {
                numk = monoStack.top();
                monoStack.pop();
            }
            monoStack.push(nums[i]);
            // -- 维护单调递减栈 --
        }
        return false;
    }
};
</code></span></code></pre>
<h4 id="1019"><a href="https://leetcode-cn.com/problems/next-greater-node-in-linked-list/">1019. 链表中的下一个更大节点</a></h4>
<p><hard>中等</hard></p>
<p><strong>题目描述：</strong></p>
<p>给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node<em>1, node</em>2, node_3, &hellip; 。</p>
<p>每个节点都可能有下一个更大值（next larger value）：对于 node<em>i，如果其 next</em>larger(node<em>i) 是 node</em>j.val，那么就有 j &gt; i 且  node<em>j.val &gt; node</em>i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。</p>
<p>返回整数答案数组 answer，其中 answer[i] = next<em i_1="i+1">larger(node</em>) 。</p>
<p>注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。</p>
<p><strong>示例 1：</strong></p>
<p>输入：[2,1,5]<br />
输出：[5,5,0]</p>
<p><strong>示例 2：</strong></p>
<p>输入：[2,7,4,3,5]<br />
输出：[7,0,5,5,0]</p>
<p><strong>示例 3：</strong></p>
<p>输入：[1,7,5,1,9,2,5,1]<br />
输出：[7,9,9,9,0,5,0,0]</p>
<p><strong>提示：</strong></p>
<p>对于链表中的每个节点，1 &lt;= node.val &lt;= 10^9<br />
给定列表的长度在 [0, 10000] 范围内</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector&lt;int&gt; nextLargerNodes(ListNode* head) {
        if (head == NULL) { 
            return vector&lt;int&gt;(); 
        }

        vector&lt;int&gt; v;
        stack&lt;int&gt; st;

        while (head != NULL) {
            v.push_back(head-&gt;val);
            head = head-&gt;next;
        }
        for (int i = 0; i &lt; v.size(); ++i) {
            while (!st.empty() &amp;&amp; v[i] &gt; v[st.top()]) {
                v[st.top()] = v[i];
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) {
            v[st.top()] = 0;
            st.pop();
        }
        return v;
    }
};
</code></span></code></pre>
<h4 id="k"><a href="https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=188&amp;tqId=38279&amp;rp=1&amp;ru=%2Factivity%2Foj&amp;qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&amp;tab=answerKey">最小的 K 个数</a></h4>
<p><strong>题目描述</strong></p>
<p>给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K&gt;数组的长度，那么返回一个空的数组。</p>
<h5 id="_11">方法一：快排</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; GetLeastNumbers_Solution(vector&lt;int&gt; input, int k) {
        if (k == 0 || k &gt; input.size()) { return vector&lt;int&gt;(); }
        quickSort(input, 0, input.size()-1);
        return vector&lt;int&gt;(input.begin(), input.begin() + k);
    }

    void quickSort(vector&lt;int&gt;&amp; arr, int sta, int end) {
        if (sta &gt; end) { return; }
        int left = sta;
        int right = end;
        int index = arr[left];

        while (left &lt; right) {
            while (left &lt; right &amp;&amp; arr[right] &gt;= index) { right--; }
            if (arr[right] &lt; index) { arr[left]  = arr[right]; }
            while (left &lt; right &amp;&amp; arr[left]  &lt;= index) { left++;  } 
            if (arr[left] &gt; index)  { arr[right] = arr[left];  }
        }
        arr[left] = index;
        quickSort(arr, sta, left - 1);
        quickSort(arr, left + 1, end);
    }
};
</code></span></code></pre>
<h5 id="_12">方法二：优先队列（小顶堆）</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">priority_queue&lt;Type, Container, Functional&gt;
/*
    Type 就是数据类型;
    Container 就是容器类型;
        （Container 必须是用数组实现的容器，比如 vector, deque 等，但不能用 list。
            STL 里面默认用的是 vector）
    Functional 就是比较的方式。
*/

// 降序队列，大顶堆（默认）
priority_queue&lt;int, vector&lt;int&gt;, less&lt;int&gt;&gt; q;
// 升序队列，小顶堆
priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; q;

/*
    greater 和 less 是 std 实现的两个仿函数。
    就是使一个类的使用看上去像一个函数。
    其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
*/
</code></span></code></pre>
<p>和队列基本操作相同：</p>
<div class="pure-table-scrollable"><table class="pure-table pure-table-horizontal">
<thead>
<tr>
<th>方法</th>
<th>内容</th>
</tr>
</thead>
<tbody>
<tr>
<td>top</td>
<td>访问队头元素</td>
</tr>
<tr>
<td>pop</td>
<td>弹出队头元素</td>
</tr>
<tr>
<td>size</td>
<td>返回队列内元素个数</td>
</tr>
<tr>
<td>empty</td>
<td>队列是否为空</td>
</tr>
<tr>
<td>push</td>
<td>插入元素到队尾 (并排序)</td>
</tr>
<tr>
<td>emplace</td>
<td>原地构造一个元素并插入队列 (并排序)</td>
</tr>
<tr>
<td>swap</td>
<td>交换内容</td>
</tr>
</tbody>
</table></div>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; GetLeastNumbers_Solution(vector&lt;int&gt; input, int k) {
        if (k &gt; input.size()) {
            return vector&lt;int&gt;();
        }

        priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; p;
        vector&lt;int&gt; re;

        for (int i = 0; i &lt; input.size(); ++i) {
            p.push(input[i]);
        }
        for (int i = 0; i &lt; k; ++i) {
            re.push_back(p.top());
            p.pop();
        }
        return re;
    }
};
</code></span></code></pre>
<h4 id="_13">两数之和</h4>
<p><strong>题目描述</strong></p>
<p>给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2。</p>
<p><strong>注意：</strong></p>
<p>下标是从1开始的。假设给出的数组中只存在唯一解 </p>
<p><strong>例如：</strong> </p>
<p>给出的数组为 {20, 70, 110, 150}，目标值为90</p>
<p>输出 index1=1, index2=2 </p>
<h5 id="map">map</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) {
        map&lt;int, int&gt; mp;
        for (int i = 0; i &lt; numbers.size(); ++i) {
            if (mp.find(target - numbers[i]) != mp.end()) {
                return {mp[target - numbers[i]], i + 1};
            }
            else {
                mp[numbers[i]] = i + 1;
            }
        }
        return {};
    }
};
</code></span></code></pre>
<h5 id="unordered_map">unordered_map</h5>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) {
        unordered_map&lt;int, int&gt; mp;
        for (int i = 0; i &lt; numbers.size(); ++i) {
            if (mp.find(target - numbers[i]) != mp.end()) {
                return {mp[target - numbers[i]], i + 1};
            }
            else {
                mp[numbers[i]] = i + 1;
            }
        }
        return {};
    }
};
</code></span></code></pre>
<h4 id="_14"><a href="https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=188&amp;tqId=38293&amp;rp=1&amp;ru=%2Fta%2Fjob-code-high-week&amp;qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&amp;tab=answerKey">最长无重复子串</a></h4>
<p><strong>题目描述</strong></p>
<p>给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。</p>
<pre><code class="pre-wrap"><span style="overflow-x: auto; max-width:100%; display:inline;"><code class="language-c++">class Solution {
public:
    int maxLength(vector&lt;int&gt;&amp; arr) {
        unordered_map&lt;int, int&gt; heap;
        int res = 0;
        for (int i = 0, j = 0; i &lt; arr.size(); ++i)
        {
            heap[arr[i]]++;
            while (heap[arr[i]] &gt; 1) {
                heap[arr[j++]]--;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};
</code></span></code></pre>
  </div>
</div>
 
    </div>
  </div>
  <div id="footer-background">
    <div id="footer">
      <div class="legal pure-g">
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-license"><a href="https://beian.miit.gov.cn/#/Integrated/index">浙ICP备2020038748号</a></p>
  </div>
  <div class="pure-u-1 u-sm-1-2">
    <p class="legal-links"><a href="https://github.com/zromyk">GitHub</a></p>
    <p class="legal-copyright">Copyright © 2021 Wei Zhou. 保留所有权利。</p>
  </div>
</div>
    </div>
  </div>
  <!-- <script src="https://cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script> -->
  <script src="/style/html/jquery.min.js"></script>
  <script src='/style/article/latex/latest.js?config=TeX-MML-AM_CHTML'></script>
<!-- <script src="https://cdn.geogebra.org/apps/deployggb.js"></script> -->
<script src="/style/article/deployggb.js"></script>
<!-- <script src="https://apps.bdimg.com/libs/highlight.js/9.1.0/highlight.min.js"></script> -->
<script type="text/javascript">
  // 脚本：navigation 随鼠标移动自动变换宽度
  var element = document.getElementById("navigation"); // 获取要操作的元素
  var elementWidth = parseInt(getComputedStyle(element).width);
  var elementLeft = 0;
  var elementRight = 0;
  element.addEventListener('mouseenter', function (event) { // 添加鼠标按下事件的监听器
    elementLeft = element.getBoundingClientRect().left - 10;
    elementRight = element.getBoundingClientRect().left + elementWidth * 3;
    window.addEventListener('mousemove', resize); // 添加全局的鼠标移动事件的监听器
  });

  function resize(event) {
    var minWidth = elementWidth;
    var maxWidth = elementWidth * 2.5;
    // console.log(elementLeft, event.clientX, elementRight, event.clientX - elementLeft + elementWidth / 2);
    if (elementLeft <= event.clientX && event.clientX <= elementRight) {
      var width = event.clientX - elementLeft + elementWidth / 2;
      width = Math.min(width, maxWidth);
      width = Math.max(width, minWidth);
      element.style.width = width + 'px'; // 设置新的宽度样式属性
    }
    else {
      element.style.width = elementWidth + 'px'; // 设置新的宽度样式属性
      stopResize();
    }
  }

  function stopResize() {
    element.style.width = elementWidth + 'px'; // 设置新的宽度样式属性
    // console.log("stopResize", elementLeft, event.clientX, elementRight, event.clientX - elementLeft + elementWidth / 2);
    window.removeEventListener('mousemove', resize); // 移除鼠标移动事件的监听器
  }
</script>
<script src="/style/article/highlight/highlight.min.js"></script>
<script type="text/javascript">
  // 脚本：code语法高亮
  hljs.initHighlightingOnLoad();
</script>
<script>
  function animateByNav() {
    $("html").animate({
        scrollTop: ($(event.target.hash).offset().top - 52)
    }, 300);
  };
</script>
<script src="/style/article/pell-1.0.6/dist/pell.js"></script>
<script>
  // 脚本：自由编辑页面
  var editor = window.pell.init({
    element: document.getElementById('editor'),
    defaultParagraphSeparator: 'p',
    onChange: function(html) {
        document.getElementById('text-output').innerHTML = html
        document.getElementById('html-output').textContent = html
    }
  });

  function markdownEditor() {
    var articles = document.getElementById('content-articles-markdown');
    if (articles.getAttribute("contenteditable") == "true") {
        articles.setAttribute("contenteditable", "false");
        document.getElementById("content-articles-markdownEditor").style.display = "none"; //隐藏
        document.getElementById("button-markdownEditor").innerHTML = "启用编辑";
    } else {
        articles.setAttribute("contenteditable", "true");
        document.getElementById("content-articles-markdownEditor").style.display = ""; //显示
        document.getElementById("button-markdownEditor").innerHTML = "关闭编辑";
    }
  };

  function save() {
      window.alert("保存成功");
  };
</script>

</body>
</html>
